BOJ_2775_부녀회장이 될테야

DP(Dynamic Programming)의 기초라고 추천 받은 문제

n층의 m호에는 n-1층의 1호~m호까지의 인원의 합이 산다
2차원 dp배열에 저장하며 인원을 구한다

n층의 m-1호에는 n-1층의 1호~m-1호까지의 합이 있기 때문에
dp[n][m] = dp[n][m-1] + dp[n-1][m];
이 된다

package BJO;  
  
import java.util.Scanner;  
  
public class BJO_2775_부녀회장이될테야 {  
  
    public static void main(String[] args) {  
       Scanner scan = new Scanner(System.in);  
  
       int T = scan.nextInt();  
       for (int i = 0; i < T; i++) {  
          // 층  
          int k = scan.nextInt();  
          // 호수  
          int n = scan.nextInt();  
  
          long[][] dp = new long[k + 1][n + 1];  
  
          // 0층의 i호에는 i명이 산다  
          for (int j = 1; j <= n; j++) {  
             dp[0][j] = j;  
          }  
  
          // 같은 층 앞 호수까지 더한 거랑  
          // 내 아래층 인원이랑 더하면 지금 호수의 인원을 구할 수 있음  
          for (int j = 1; j <= k; j++) {  
             for (int l = 1; l <= n; l++) {  
                dp[j][l] = dp[j - 1][l] + dp[j][l - 1];  
             }  
          }  
  
          System.out.println(dp[k][n]);  
       }  
    }  
}

#dp